/**
 * 29. 两数相除
 * https://leetcode-cn.com/problems/divide-two-integers/
 */
public class Solutions_29 {
    public static void main(String[] args) {
//        int dividend = 10, divisor = 3;  // output: 3
//        int dividend = 20, divisor = 3;  // output: 6
//        int dividend = 7, divisor = -3;  // output: -2
//        int dividend = -2147483648, divisor = -1;  // output: 2147483647
        int dividend = -2147483648, divisor = 2;  // output: -1073741824
//        int dividend = -2147483648, divisor = 1;  // output: -2147483648

        int result = divide(dividend, divisor);
        System.out.println(result);
    }

    /**
     * 解题思路：位运算实现除法、乘法
     * 例如：dividend = 20，divisor = 3，结果为 20 / 3 = 6
     * 20 = 0b10100
     *  3 = 0b00011
     *
     * 1. 20 >> 31 = 0，小于 3，无法相除
     * ...
     * 2. 20 >> 5 = 0，小于 3，无法相除
     * 3. 20 >> 4 = 1(0b0001)，小于 3，无法相除
     * 4. 20 >> 3 = 2(0b0010)，小于 3，无法相除
     * 5. 20 >> 2 = 5(0b0101)，大于 3，可以相除
     *      那么 res += 1 << 2，即 2 * 2 = 4，res = 4
     *      同时 20 - (3 << 2) = 12，即 20 - 3 * 4 = 8
     * 6. 8 >> 1 = 4(0b0100)，大于 3，可以相除
     *      那么 res += 1 << 1，即 2 * 1 = 2，res = 6
     *      同时 8 - (3 << 1) = 10，即 8 - 3 * 2 = 2
     * 7. 2 >> 0 = 2，小于 3，无法相除
     */
    public static int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        // 记录下符号位
        boolean negative = false;
        int res = 0;
        if ((dividend ^ divisor) < 0) {
            // 假如有一位是负数，异或后，二进制的符号位还是 1
            // 否则，两位都是正数，或者两位都是负数的情况，异或后，一定是正数，即大于等于 0
            negative = true;
        }
        // 将两数都转换成正数计算（提升为 long 值，否则 -2147483648 的绝对值还是 -2147483648）
        long m = Math.abs((long) dividend);
        long n = Math.abs((long) divisor);

        /**
         * 右移 1 位，即是除 2，右移 2 位，即是除 4...
         * 左移 1 位，即是乘 2，左移 2 位，即是乘 4...
         */
        for (int i = 31; i >= 0; i--) {
            // 位运算实现除法
            long j = m >> i;
            if (j >= n) {
                // 位运算实现乘法
                long k = 1 << i;
                // 除之后的商仍然大于等于 n，说明可以相除
                res += k;
                // m 减去相应的数值
                m -= n << i;
            }
        }
        return negative ? -res : res;
    }
}
